package com.just.fun.arithmetic;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 打印字符串的所有可能性
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输 入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba
 * 思路：将当前位置的字符和前一个字符位置交换，递归
 */
public class Permutation {

    public static void main(String[] args) {
        System.out.println(getAllStr("abc"));
    }
    public static ArrayList<String> getAllStr(String str){
        ArrayList<String> resultList=new ArrayList<>();
        if(str==null || str.equals("")){
            return resultList;
        }
        helper(str.toCharArray(),0,resultList);
        Collections.sort(resultList);
        return resultList;
    }
    //递归
    public static void helper(char[] s,int index,ArrayList<String> res){
        if(index==s.length-1){
            res.add(String.valueOf(s));
            return;
        }
        for (int i = index; i < s.length; i++) {
            if(i==index||s[index]!=s[i]){
                //交换
                swap(s,index,i);
                //下一个递归
                helper(s,index+1,res);
                //换回来
                swap(s,index,i);
            }
        }

    }

    public static void swap(char[] s,int a,int b){
        char tmp=s[a];
        s[a]=s[b];
        s[b]=tmp;
    }
}
